package showtime.framework.algorithm.collections
{

	/**
	 * 
	 * @author 绿豆蛙
	 * 
	 */	
	public class BinaryHeap
	{
		private var _data:Array = null;
		/**
		 * CompareValue 
		 */		
		private var _compareValue:String = null;
		/**
		 * Default sort method 
		 */		
		public var sortMethod:Function = defaultSortMethod;
		
		/**
		 * Constructor
		 *  
		 * @param compareValue
		 * 
		 */		
		public function BinaryHeap( compareValue:String = null)
		{
			_data = [];
			_compareValue = compareValue;
		}

		public function push( node:Object ):void
		{
			_data.push( node );

			if( length > 1 )
			{
				var index:int = length;
				
				var parentIndex:int = index / 2 - 1;
				
				var parent:Object = null;
	
				while(defaultSortMethod(node, _data[parentIndex]))
				{
					parent = _data[parentIndex];
					_data[parentIndex] = node;
					_data[index - 1] = parent;
					index /= 2;
					parentIndex = index / 2 - 1;
				}
				
			}
			
		}
		
		/**
		 * Shift the first node. 
		 * @return 
		 * 
		 */		
		public function shift():Object
		{
			var result:Object =  _data.shift();
			
			if( length > 1 )
			{
				var lastNode:Object = _data.pop();
				
				_data.unshift(lastNode);
				
				var index:int = 0;

				var childIndex:int = (index + 1) * 2 - 1;

				var comparedIndex:int = 0;
				
				var parent:Object = null;

				while( childIndex < length )
				{
					if( childIndex + 1 == length )
					{
						comparedIndex = childIndex;
					}
					else
					{
						comparedIndex = sortMethod(_data[childIndex], _data[childIndex + 1]) ? childIndex : childIndex + 1;
					}
					
					if(sortMethod(_data[comparedIndex], lastNode))
					{
						parent = _data[comparedIndex];
						_data[comparedIndex] = lastNode;
						_data[index] = parent;
						index = comparedIndex;
						childIndex = (index + 1) * 2 - 1;
					}
					else
					{
						break;
					}
				}
			}
						
			return result;
		}

		/**
		 * 更新节点
		 *  
		 * @param node
		 * 
		 */		
		public function update(node:Object):void
		{
			var index:int = _data.indexOf(node) + 1;
			
			if( index == 0 )
			{
				throw new Error("[Binary Heap] update node not exist.");
			}
			else
			{
				var parentIndex:int = index / 2 - 1;
				var parent:Object = null;

				while(sortMethod(node, _data[parentIndex]))
				{
					parent = _data[parentIndex];
					_data[parentIndex] = node;
					_data[index - 1] = parent;
					index /= 2;
					parentIndex = index / 2 - 1;
				}
			}
		}
		
		/**
		 * Index of the node you choose.
		 *  
		 * @param node
		 * @return 
		 * 
		 */		
		public function indexOf(node:Object):int
		{
			return _data.indexOf(node);
		}
		
		
		public function get length():uint
		{
			return _data.length;
		}
		
		private function defaultSortMethod(node1:Object, node2:Object):Boolean
		{
			if( _compareValue != null)
			{
				return node1[_compareValue] < node2[_compareValue];
			}
			else
			{
				return node1 < node2;
			}
			return false;
		}
		
		
	}
}